Text Justification

Understand and solve the interview question "Text Justification".

Description#

We are given an array of strings and a maximum width. We have to format the input words in the same order and into several rows with n columns. The words must be formatted such that each line has exactly n characters, one in each column, except possibly the last line. We must squeeze as many words as possible into each line, with at least one space between each pair of consecutive words. The first word on each line must start at the left-most column.

The last word on each line must end at the right-most column, unless only one word can fit on a line. More than one space between words may need to be inserted to ensure that the first word in a line starts at the first column and the last word ends at the last column. In such cases, we will insert an approximately equal number of spaces between each pair of words. If the spaces can’t be evenly spread between the words on a line, then the first two words will get more spaces than all the other word pairs, which will be spaced equally.

The last line must start on the left-most column, but may end before the last column. Only one space between each pair of words must be used on the last line. We will put as many words as we can in each line. We will add extra spaces, when necessary, so that each line has exactly the given width of characters. We will distribute extra spaces between words as evenly as possible. Otherwise, the empty slots on the left will have more spaces than the slots on the right.

Note: A word consists of non-space characters only. Each word’s length must be greater than 0 and should not exceed the given width. The input array will contain at least one word.

Constraints#

  • 1 <= words.length <= 300
  • 1 <= words[i].length <= 20
  • 1 <= width <= 100
  • words[i].length <= width
  • words[i] consists of only English letters and symbols.

Let’s see the example in the following illustration:

Input = ["The", "important", "is", "not", "to", "stop", "questioning"]
Input = ["The", "important", "is", "not", "to", "stop", "questioning"]
Output = [ 'The important is',
'not to stop',
'questioning ' ]

Output = [ 'The important is',...
Viewer does not support full SVG 1.1
Text justification example

Coding exercise#

Text justification exercise

Solution#

We have an array of words and a maximum line width. We will put words in a line by traversing the array, and each line length will be equal to the given width.

Let’s see the algorithm that is used to implement the problem described above:

  • First, we will find out where to cut the array of words by setting the given width as a threshold.

  • Generally, we will use a single space between words to make a line.

  • If extra space exists at the end of the line, we will evenly distribute the spaces between the words.

  • We will compute the extra spaces by subtracting the given width from the current line length and then dividing it by (j - 1 - i) + 1, where j will represent the current line length and i will represent the current string index of the given array.

  • Next, we will add the extra spaces between the words of the current line.

  • For the last line, we will add a single space between the words and add the extra spaces after the last word of the line.

Let’s understand this algorithm with the illustration given below:

Created with Fabric.js 3.6.6
Justify the text

1 of 26

Created with Fabric.js 3.6.6
Justify the text

2 of 26

Created with Fabric.js 3.6.6
Justify the text

3 of 26

Created with Fabric.js 3.6.6
Justify the text

4 of 26

Created with Fabric.js 3.6.6
Justify the text

5 of 26

Created with Fabric.js 3.6.6
Justify the text

6 of 26

Created with Fabric.js 3.6.6
Justify the text

7 of 26

Created with Fabric.js 3.6.6
Justify the text

8 of 26

Created with Fabric.js 3.6.6
Justify the text

9 of 26

Created with Fabric.js 3.6.6
Justify the text

10 of 26

Created with Fabric.js 3.6.6
Justify the text

11 of 26

Created with Fabric.js 3.6.6
Justify the text

12 of 26

Created with Fabric.js 3.6.6
Justify the text

13 of 26

Created with Fabric.js 3.6.6
Justify the text

14 of 26

Created with Fabric.js 3.6.6
Justify the text

15 of 26

Created with Fabric.js 3.6.6
Justify the text

16 of 26

Created with Fabric.js 3.6.6
Justify the text

17 of 26

Created with Fabric.js 3.6.6
Justify the text

18 of 26

Created with Fabric.js 3.6.6
Justify the text

19 of 26

Created with Fabric.js 3.6.6
Justify the text

20 of 26

Created with Fabric.js 3.6.6
Justify the text

21 of 26

Created with Fabric.js 3.6.6
Justify the text

22 of 26

Created with Fabric.js 3.6.6
Justify the text

23 of 26

Created with Fabric.js 3.6.6
Justify the text

24 of 26

Created with Fabric.js 3.6.6
Justify the text

25 of 26

Created with Fabric.js 3.6.6
Justify the text

26 of 26

Let’s look at the code for this solution:

Text justification solution

Complexity measures#

Time complexity Space complexity
O(n)O(n) O(1)O(1)

Time complexity#

We will traverse the given array of words exactly once, so the time complexity will be O(n)O(n), where n will be the size of the array.

Space complexity#

The space complexity will be O(1)O(1) for this problem.

Reconstruct Itinerary

Gas Station